import java.util.HashMap;
import java.util.Map;

public class Main {
    static class TreeNode {
        char val;
        TreeNode left, right;

        TreeNode(char val) {
            this.val = val;
        }
    }

    public static void main(String[] args) {
         String inorder = "BDCA";
        String postorder = "BADC";
        TreeNode root = buildTree(inorder, postorder);

        System.out.println(preorderTraversal(root));
    }

    // 根据中序遍历和后序遍历构建二叉树
    static TreeNode buildTree(String inorder, String postorder) {
        Map<Character, Integer> indexMap = new HashMap<>();
        for (int i = 0; i < inorder.length(); i++) {
            indexMap.put(inorder.charAt(i), i);
        }
        return buildTreeHelper(inorder, 0, inorder.length() - 1, postorder, 0, postorder.length() - 1, indexMap);
    }

    static TreeNode buildTreeHelper(String inorder, int inStart, int inEnd, String postorder, int postStart, int postEnd, Map<Character, Integer> indexMap) {
        if (inStart > inEnd || postStart > postEnd) {
            return null;
        }
        char rootVal = postorder.charAt(postEnd);
        TreeNode root = new TreeNode(rootVal);
        int rootIndex = indexMap.get(rootVal);
        int leftTreeSize = rootIndex - inStart;

        root.left = buildTreeHelper(inorder, inStart, rootIndex - 1, postorder, postStart, postStart + leftTreeSize - 1, indexMap);
        root.right = buildTreeHelper(inorder, rootIndex + 1, inEnd, postorder, postStart + leftTreeSize, postEnd - 1, indexMap);

        return root;
    }

    // 前序遍历二叉树
    static String preorderTraversal(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        preorderTraversalHelper(root, sb);
        return sb.toString();
    }

    static void preorderTraversalHelper(TreeNode root, StringBuilder sb) {
        if (root == null) {
            return;
        }
        sb.append(root.val);
        preorderTraversalHelper(root.left, sb);
        preorderTraversalHelper(root.right, sb);
    }
}
